The present invention concerns the field of digital transmissions.
We consider the transmission of digital data, i.e. in the form of symbols taking a finite number ND of values d0, . . . ,dNDxe2x88x921, and discrete in time: it is therefore a digital symbol sequence Dm (m=0,1,2,etc.) belonging to a defined alphabet {di, 0xe2x89xa6i less than ND}.
The role of the detector, in terms of the present invention, is to provide estimations of successive symbols Dm in a sequence to be detected from an xe2x80x9cencodedxe2x80x9d observation signal available at a receiver. The xe2x80x9cencoderxe2x80x9d, which provides the observation signal representing the sequence to be detected to the detector must be taken in the most general sense: it can be seen as a black box, developed by the designer or not. It may be an error correcting encoder (in this case, the observation signal is also a digital signal, and the xe2x80x9cdetectorxe2x80x9d is a correcting decoder), or the compound of a correcting encoder-modulator-propagation channel-demodulator (the observation signal is then a digital sequence marred by errors), or else the more straightforward compound of a modulator-propagation channel (the xe2x80x9cdetectorxe2x80x9d is then a demodulator).
The detector has hard inputs if the observation signal which it processes is a digital sequence of symbols with discrete values, and soft inputs if the observation signal is a sequence of sampled and quantified values, or of discrete estimations accompanied by respective weights representing the degrees of confidence vested in these estimations.
The detector has soft outputs if the symbol estimations which it delivers are accompanied by respective weights representing the degrees of confidence vested in these estimations, and hard outputs if it simply delivers discrete estimations.
In real transmission systems, it is common to process signals having a memory, i.e. the signal segment carrying the data at a given moment depends not only on this data at the same moment, but also on the past data or past signal segments. If this memory verifies certain properties, particularly the fact that a trellis exists describing the production process of the observation signal, then the receiver can determine the data symbols carried by the observation signal in the sense of maximum likelihood, by means of the Viterbi algorithm (see G. D. Forney, Jr., xe2x80x9cThe Viterbi Algorithmxe2x80x9d, Proc. IEEE, Vol.61, No.3, March 1973, pages 268-278) or the MAP (Maximum A Posteriori) algorithm also set out in the article by G. D. Forney.
Different versions of the MAP algorithm are described in the following references: K. Abend and B. D. Fritchman, xe2x80x9cStatistical Detection for Communication Channels with Intersymbol Interferencexe2x80x9d, Proc. IEEE, Vol.58, No.5, May 1970, pages 779-785; R. W. Chang and J. C. Hancock, xe2x80x9cOn Receiver Structures for Channels Having Memoryxe2x80x9d, IEEE Trans. on Information Theory, Vol.IT-12 No.4, October 1966, pages 463-468; and L. R. Bahl et al, xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol Error Ratexe2x80x9d, IEEE Trans. on Information Theory, Vol.IT-20, March 1974, pages 284-287.
It also happens that xe2x80x9cencodersxe2x80x9d COD1,COD2, . . . ,CODN are cascaded in transmission systems (for example several error correcting encoders, or one or several error correcting encoders followed by a modulator and a propagation channel), often with intermediate interleaving operations. In this case (concatenated memory system), the receiver under consideration may consist of a cascade of elementary decoder/detectors DECN,DECNxe2x88x921, . . . ,DEC1. This receiver is optimal in the sense of maximum likelihood if the decoder/detectors DECp have soft outputs (for p greater than 1) and soft inputs, whereby the decoder/detector DECp (p greater than 1) associates with each discrete estimation of a decoded symbol Dm of the sequence to be detected (this sequence is the one delivered by the encoder CODpxe2x88x921) a weight represented by the likelihood equal or proportional to the logarithm of the ratio between the probability that the symbol Dm of the unknown sequence does in fact correspond to its estimation provided by the decoding and the probability that the symbol Dm is different from its estimation, the probabilities in question being conditional probabilities, with the knowledge of the available observation signal. In this case, the soft outputs of each decoder/detector constitute the xe2x80x9cobservation signalsxe2x80x9d for the next decoder/detector, and the likelihood data is not lost.
The advantage of the Viterbi algorithm is that its implementation by a circuit or a processor entails no great difficulties. given the straightforwardness of the operations involved: multiplications, additions/subtractions, comparisons. Furthermore, the regularity of the trellis often enables the use of tricks for programming or organising the memory, which make the algorithm even easier to implement. This explains why its use is today widespread in different categories of detector. But, in its traditional version, it does not provide the likelihood of the discrete estimations which it delivers, so that it does not allow optimal processing in the case of a concatenated memory system.
On the other hand, the MAP algorithm, in essence, provides the likelihoods of the symbols that it estimates, but poses serious difficulties of implementation: exponential quantity calculations, need to know the noise variance, sensitivity to errors in this variance, problems of digital analysis for its very low values etc.
For the concatenated memory systems mentioned above, several methods have been proposed for weighting the estimations produced by a Viterbi detector. Examples of such methods, referred to as xe2x80x9cSOVAxe2x80x9d (Soft Output Viterbi Algorithm), are:
a method consisting in taking as the likelihood of an estimation the difference between the metric accumulated at a node of the trellis corresponding to this estimation and the metric of the best path corresponding to a different discrete estimation (see C. Berrou et al, xe2x80x9cA Low Complexity Soft-Output Viterbi Decoder Architecturexe2x80x9d, Proc. ICC""93, Geneva, May 1993). This straightforward technique is commonly employed, but very sub-optimal;
the Hagenauer algorithm, described in J. Hagenauer and P. Hoeher, xe2x80x9cA Viterbi Algorithm with Soft-Decision Outputs and its Applicationsxe2x80x9d, Proc. Globecom""89, Dallas, November 1989, pages 47.1.1-47.1.7;
the Battail algorithm, described in U.S. Pat. No. 4,328,582;
the optimal (OSA) or sub-optimal (SSA) SOVA described in Y. Li, B. Vucetic and Y. Sato, xe2x80x9cOptimum Soft-Output Detection for Channels with Intersymbol Interferencexe2x80x9d, IEEE Trans. on Information Theory, Vol. IT-41, No.3, May 1995, pages 704-713.
Except for the OSA, each of these SOVA methods bring a degradation of performance compared with the MAP algorithm.
The Hagenauer, Battail and Li, Vucetic and Sato algorithms are similar to the MAP in that they carry out the calculations in the probability domain. As a result, they involve the calculation of exponentials, which makes their implementation by means of circuits or processors unattractive, even if the exponential quantities are replaced by approximations.
A primary object of the present invention is to propose a SOVA method of reasonable complexity, allowing an evaluation of likelihoods of symbols estimated by a Viterbi detector, and which brings little error probability degradation compared with the optimal case of the MAP algorithm.
This invention thus proposes a method for detecting a discrete symbol sequence from an observation signal the production of which can be described by means of a trellis of NE states Ee (0xe2x89xa6e less than NE) and NB branches Bb (0xe2x89xa6b less than NB), each branch having a start state and an arrival state among the NE states and being associated with a single Q-uplet of discrete symbols, Q being an integer at least equal to 1,
the trellis comprising paths each formed by a succession of branches, each path having a metric defined by a sum of elementary metrics relative to the successive branches which form it, and being associated with a single possible sequence of discrete symbols formed by the succession of Q-uplets with which the successive branches forming said path are respectively associated,
wherein the observation signal is processed by successive time segments, the processing of a segment n of the observation signal including.
for each of the NB branches Bb (0xe2x89xa6b less than NB), obtaining an elementary metric corresponding to a combination between the segment n of the observation signal and a reference signal associated with the branch Bb, and the calculation of an accumulated branch metric MBAb(n) by adding the elementary metric obtained to an accumulated state metric MEAe(nxe2x88x921) relative to the start state Ee of the branch Bb; and
for each of the NE states Ee (0xe2x89xa6e less than NE), updating the accumulated state metric MEAe(n), taken as equal to an optimum of the accumulated branch metrics MBAb(n) relative to those of the branches Bb which have the state Ee as the arrival state, and storing an identification of a surviving branch for which said optimum is reached,
wherein, after processing successive segments of the observation signal, a selection is made of one of the NE states Ee0 and of an optimal path xcex1opt of the trellis formed by returning up the surviving branches from the selected state, and at least one discrete symbol Dm of the sequence to be detected is estimated by the value of a corresponding symbol of the sequence with which the selected optimal path is associated,
and wherein, for each symbol Dm of the sequence to be detected, estimated after the selection of a state Ee0 and of an optimal path xcex1opt, a minimum difference in metrics is calculated between the optimal path and a competitor path associated with a sequence in which the symbol corresponding to the symbol Dm has a value other than the estimation retained for the symbol Dm and the likelihood xcex9m of the estimation of the symbol Dm is determined as a function of the calculated minimum difference in metrics.
The likelihood xcex9m of the estimation of a symbol Dm may particularly be taken as equal or proportional to the minimum difference in metrics calculated for this symbol.
The inventors have observed (by simulation) that this detection method gives performances close to the MAP as regards the error rate. Its other advantage is that it uses the same type of straightforward processes as the conventional Viterbi algorithm (only additions/subtractions and comparisons). It is of comparable complexity: the number of calculations required to obtain the likelihoods is approximately equivalent to that required by the discrete output Viterbi algorithm. But it has the great advantage of producing the likelihoods of the decisions. It is known that on a simple Gaussian channel, there may be a saving of up to nearly 3 dB (for the large signal-to-noise ratios) on each of the decoding stages. There is therefore great benefit in having such a process available.
The applications targeted are decoding concatenations, including:
demodulation of a memory system, which is to be followed by soft input decoding of a convolutional code (with or without interleaving) or of a block code; the memory system may be a transmission on a channel with inter-symbol interference, and/or a linear or continuous phase modulation (CPM, an example of which is GMSK: xe2x80x9cGaussian minimum shift keyingxe2x80x9d);
two (or more) soft decodings of concatenated convolutional codes (with or without the presence of interleaving between the codes); an example of application in this case is the decoding of turbo-codes; or else the soft decoding of a convolutional code followed by the soft decoding of a block code;
the soft decoding of a convolutional code, followed by an image or speech decoder, which would need to know the quality of the decoded symbols (binary or not), so as to improve the quality of the restored signal (example: speech decoder in a GSM-type cellular radio-communication system);
in a pattern recognition system (recognition of images, characters or speech) using modelling by hidden Markov chains (and which therefore generally uses a Viterbi algorithm to make its decision) and needing to know the decision likelihood (for example so as not to make a decision in the event of the likelihood not reaching a certain threshold).
In a preferred version of the method, during the processing of L0+L1 successive time segments nxe2x88x92r of the observation signal up to a segment n (n-L0-L1 less than nxe2x88x92rxe2x89xa6n), L0 being a positive or zero integer and L1 being a strictly positive integer, for each branch b (0xe2x89xa6b less than NB) is stored the difference xcex4b(nxe2x88x92r)=|MBAb(nxe2x88x92r)-MEAe(nxe2x88x92r)| between the accumulated branch metric MBAb(nxe2x88x92r) and the accumulated state metric MEAe(nxe2x88x92r) updated for the arrival state Ee of the branch Bb. After the processing of L1 successive segments of the observation signal up to a segment n and the selection of a state Ee0, a recursive-calculation is made on the basis of the differences in metrics stored during the processing of the previous L0+L1 segments nxe2x88x92r (nxe2x88x92L0xe2x88x92L1 less than nxe2x88x92rxe2x89xa6n), in order to determine the minimum difference in metrics relative to each symbol Dm estimated by means of the sequence with which is associated the optimal path determined by returning up the surviving branches from the state selected.
In these conditions, it is possible, after the processing of L1 successive segments of the observation signal up to a segment n and the selection of a state, to estimate Qxc3x97L1 symbols Dm relative to the previous L1 segments nxe2x88x92r such as nxe2x88x92L0xe2x88x92L1 less than nxe2x88x92rxe2x89xa6nxe2x88x92L0, and to determine the respective likelihoods of the estimations of these Qxc3x97L1 symbols Dm, the estimations of Q symbols relative to a previous segment nxe2x88x92r being formed respectively by the values of the Q-uplet of symbols with which is associated the (r+1)-th surviving branch of the optimal path covered by returning from the selected state.
The parameters L0 and L1 are chosen according to the compromise being sought between the storage space needed to run the process and the amount of calculation to be made.
To advantage, once a state Ee0 has been selected after the processing of L1 successive segments of the observation signal up to a segment n, state notes Xe relative to the NE states Ee (0xe2x89xa6e less than NE) are initialised according to Xe=|MEAe(n)xe2x88x92MEAe0(n)|, then the following operations are performed for each value of the integer r ranging from 0 to L0+L1xe2x88x921:
the selection of the surviving branch Bb0 stored, for the selected state EeO, during the processing of the segment nxe2x88x92r, followed by the updating of the selected state Ee0 taken as being the start state of the surviving branch selected Bb0;
for each of the NB branches Bb (0xe2x89xa6b less than NB), the calculation of a branch node Zb by adding to the state node Xe relative to the arrival state Ee of the branch Bb the difference in metrics xcex4b(nxe2x88x92r) stored for the branch Bb;
for each of the NE states Ee (0xe2x89xa6e less than NE), the updating of the state node Xe, taken as equal to the smallest of the branch nodes Zb calculated for those of the branches Bb which have the state Ee as the start state;
if rxe2x89xa7L0, the estimation of Q symbols of the sequence to be detected, by the values of the Q-uplet of symbols with which the surviving branch selected Bb0 is associated; and
if rxe2x89xa7L0, for each estimation di accepted for one of the Q symbols Dm, the determination of the minimum difference in metrics as being the smallest of the branch nodes Zb calculated for those of the branches Bb which are associated with Q-uplets the symbol of which corresponding to the symbol Dm has a value di different from the estimation di.
Another aspect of the present invention relates to a Viterbi processor, including elementary metrics calculation means and sequential processing means adapted to the implementation of the method above. Such a Viterbi processor may particularly be part of a digital signal demodulator, or else of a decoder such as an error correcting decoder.